The present invention relates to a method and apparatus for the insertion, and subsequent decoding, of coded information into images.
It is known to insert codes into images for example video transmissions or video clips or stills transmitted across a telecommunication link, for the purpose of identifying the owner of the images. There are a number of known schemes for inserting identification codes into the sync periods, and more recently it has been proposed to insert identification codes into the image itself, but in such a manner that the code cannot be detected by the eye.
All of the schemes heretofore proposed suffer from the disadvantage that low pass filtering and other processes such as data compression, which may occur in image compression algorithms or transmission across a telecommunication link may remove the code or degrade it to an extent where it cannot be recognised.
EP-A-0581317 discloses a scheme wherein relative extrema of intensity within the image are detected and the intensity values are modified by a certain amount. This provides a large number of sites within the image and a signature is created by modifying the value of intensity at selected sites. Although it is claimed that this method is resistant to certain types of image processing, nevertheless a more robust scheme for transmission e.g. broadcasting is desirable. Further, a disadvantage with this method is that in order to recover the encoded digital signature, it is necessary to have to hand the original image; this severely limits the application of the method.
WO 95/14289, published on May 26, 1995, discloses the embedding of an identification code throughout an image by modulating a digitised version of the image with a small noise signal. The specific system described suffers from the disadvantage of requiring to hand the original image for code identification. Further improvements in code robustness for transmission over telecommunications links or broadcasting are also desirable.
WO 95/20291, published on Jul. 27, 1995, discloses a method of hiding copyright related messages with a digital data work, which relies on commonly occurring patterns or sequences of data in the work acting as signposts to target data elements which are modified according to certain rules. The disclosed method suffers from a lack of robustness to signal degradation.
All of the above references suffer from a disadvantage that they are concerned wholly or principally with the digital domain, and the disclosed techniques are not suited to the analog domain, in particular where digital to analog conversion and analog to digital conversion may easily lose or degrade individual pixel values.
WO 89/08915 discloses an invasive coding technique in which insignificant digits of recorded material are replaced with a code digit from an independent sequence. WO 90/09663 discloses a non-invasive technique wherein data words are identified according to predetermined criteria and a unique identifying pattern is created therefrom. Neither of these techniques is well suited to practical use such as in broadcasting applications.
An object of the present invention is to provide a highly robust method of encoding information into an image, which is highly resistant to image manipulation and degradation and is effective equally in analog and digital domains.
The present invention is based in one aspect on the realisation that coded information may be inserted into an image in strongly featured regions of the image in such a way that the code is resistant to image compression and/or low pass filtering such as may occur in transmission over telecommunication links, but is not visible to the eye, and furthermore the code does not require for decoding the presence of the original image.
In a first specific aspect, the invention provides a method for inserting coded information into an image, comprising analysing the image, identifying strongly featured regions and inserting coded information into these regions.
By strongly featured regions is meant, for the purposes of this specification, regions of primary strength to which the eye responds in viewing an image for example textured regions or lines or boundaries between two regions of different luminance, wherein in such regions, it is possible to insert a relatively large amount of information without significantly altering the image in its appearance to the eye; such regions will be referred to herein as "strongly featured region(s) as defined herein". It is possible in some applications in order for an adequate prospect of decoding the code, that the code is inserted at an intensity which may risk some visible artefact; nevertheless the present invention always permits the possibility of completely invisible code insertion.
Because the method of the invention relies on an analysis of the entire image and code being inserted in strongly featured regions rather than in individual pixels as in the prior art, the code is better able to survive analog to digital conversions and digital to analog conversions, where there will inevitably be pixel misalignments. between the original and processed images, and hence the pixel values will be apparently altered.
As preferred, edge regions between areas of different luminance are employed since these are very distinctive and will permit code insertion without visibly degrading the image. However, edge regions between areas of different chrominance may alternatively or in addition be employed. In a further preferred form, textured regions may be employed as will hereinafter be described.
As preferred, the coded information is inserted into strongly featured regions by altering the structure of the image in such region in a predictable or identifiable manner. The structure of the image may be altered by inserting a distinct subimage, for example a rectangular bar or ellipse along the length of an edge region. Alternatively and as preferred, the image is altered by applying an insert function to an area including the strongly featured region, which insert function gradually decreases in intensity from the centre of its region of application, so as to blend with the surrounding region.
A main advantage of applying the coded information by altering the image in a predictable or identifiable manner is that the information can be recovered in a decoding process at a remote location without having the original to hand. Thus, upon decoding, the image is analysed and a search is made for any feature resembling the structural alteration. If one or more features can provisionally be identified, then such features can be regarded as coded information; as preferred a "confidence factor" may be attached to each detected feature denoting the degree of reliability of the identification.
Prior to inserting the information, the image is preferably analysed to determine at least one masking threshold or masking parameter which provides a measure of by how much the structure of the image may be altered without risking the coded information becoming visible. If such threshold or parameter is sufficient to enable insertion of coded information of sufficient intensity to permit decoding, the coded information is inserted at a level determined by the masking parameter or threshold.
Thus as preferred an assessment is made of the strength or energy of the strongly featured regions within the image, in order to determine the permissible strength of insertion. This assessment value is employed to appropriately scale the insert function as it is inserted into the image. Further masking thresholds may be provided by assessing whether the image is suitable for code insertion, for example the degree of consistency of the edge, the definition of the edge centre, and the strength to prevent insertions when the image is determined to be unsuitable.
Thus in a more specific aspect, the invention provides a method for inserting coded information into an image, comprising analysing the image, identifying strongly featured regions, determining for at least one such region a masking parameter, and inserting coded information into such region in a predictable or identifiable manner by an amount determined by said masking parameter.
As preferred the coded information is inserted into an edge region by varying the luminance intensity in a local area, along the length of an edge, for example, by applying over the area a luminance intensity having a non-linear contour, for example a concave or convex function, which is aligned with the edge. A function applied in this way may represent a digital "1" or "0" according to whether it is concave or convex (for the purposes of this specification, where the terms concave, concavity and concaveness are used, they are to be understood as including convexity, which may be regarded as concavity with a negative radius of curvature). Such a method is very resistant to signal degradation arising for example from image compression. Other methods of encoding may be envisaged for example applying a non-linear function which varies perpendicular to the edge.
For textured regions, an example of which is a carpet with several colours distributed at random in the carpet fibre, a code would be inserted by first performing a statistical cluster analysis on the image to identify regions which consist of two or more basic values which are randomly distributed. The most intense "foreground" value is determined, and a circular function, appropriately scaled by a suitable masking parameter, centred in the textured region and gradually diminishing to zero radially, is applied to the foreground pixels to modulate their intensities. In the decoding process, a similar analysis is applied to the image, and the set of foreground pixels in each textured region is analysed to assess whether such circular function has been applied.
As preferred, the image, e.g. a video frame or field, is divided up into a number M.times.N of blocks in M rows and N columns, each block comprising n.times.n pixel elements (e.g. 8.times.8). Strongly featured regions are searched in each block for insertion of code. In order to encode a significant amount of information into an image, it is necessary to apply the insertion function to a number of featured regions, say edges, in the image. If for example, one edge is chosen in each block into which the image is divided, then in order to increase confidence when attempting to recognise the code, the edges in one row may be encoded according to two separate pseudo-random codes, representing a "1" or "0". Thus when an image is scanned for a code, the insertion function in each block may or may not be located with a degree of confidence. The identified functions for a row of blocks, with appropriate confidence weighting factors, are compared with the pseudo-random codes to derive a "1" or "0" with a much higher confidence factor.
However as preferred and as an alternative to relying on rows of blocks, each row representing one bit, the various blocks which together represent one bit, may be distributed throughout the image according to a further predetermined code. Thus, when decoding an image, knowledge of the predetermined code enables the blocks to be grouped together for analysis with the pseudo random codes to determine the value of the bit. This method has the advantage that areas where no edges occur, for example background regions of sky, can be avoided.
Although two pseudo random codes of ones and zeros are preferred for decoding data, other pseudo random codes may be employed. For example, a single pseudo random code may be employed where a watermarking type code is required indicating ownership of the image. Other types of code may also be employed.
A problem with dividing an image into a number of blocks occurs in decoding the image, since if there are only a few edges in the image and many blocks without an edge, it is difficult to maintain synchronisation with the encoding process.
As a means of overcoming this problem, the video synchronisation process may be altered so that synchronisation occurs at the start of each row or line of blocks; if then as described above, each row represents a single bit of information, a secure method of coding is provided. One means of providing synchronisation information, for example, where video images are employed, is to use the line sync pulses as a method of synchronisation. As an alternative, a very low frequency modulation may be applied to an entire image (for example a digitised still photograph image) so that there is provided a part of a cycle or one or two cycles of a low frequency modulation across the width and/or height of the image to enable centering of the decoding process onto this low frequency modulation, in a manner somewhat analogous to an archer's target. In any event, the decoding stage will automatically align to the reception of digital information to permit the required synchronisation.
In regions of the image where there does not occur strong features, for example background regions, it may be desired to insert a code in the form of a region of fixed or variable luminance, for example a circle which although relatively large in size, is not visible to the eye. This ensures that coding information is present in all parts of an image for robustness of transmission and decoding.
In a further specific object therefore the present invention provides a method of coding information into an image, dividing the image in M.times.N blocks in N rows and M columns, and inserting into selected blocks code information of one of a plurality of types, the type of code inserted depending on an assessment of the image features in the respective block.
The present invention also extends to a method of decoding, and according the invention provides in a further aspect a method of decoding information contained in an image, the method comprising analysing the image, identifying strongly featured regions, determining for at least one such region an anticipated insertion of coded information, and correlating such anticipated insertion with the image to determine whether there has been inserted into the strongly featured region coded information.
As preferred in the decoding method, similar processing steps are carried out as in the encoding method, involving analysing the image and defining an anticipated insertion function, as will become clear in the description of the preferred embodiment.
The present invention also extends to apparatus for carrying out any of the aforesaid aspects of the invention.
The information encoded into an image may be used for a variety of purposes, for example as follows:
to insert copyright or identification information in video clips or films; PA1 to insert copyright or identification information into stills; PA1 to log when adverts or films are played in broadcasts, for monitoring purposes; PA1 to identify the master copy from which pirated videos are copied.
The information encoded may represent coding information which initiates operations within the decoding apparatus, or provides specific identification information, for example copyright information with the name of the copyright owner etc. Alternatively, the information may be merely analogous to a watermark, serving merely to identify the source of the image information but not being specific to the particular image.